package demo2;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-09-02
 * Time: 20:37
 */

import java.util.Arrays;

/**
 * 插入排序
 */
public class InsertSort {
    /**
     * 插入排序思想 : 将待排序的记录按照其关键字的大小逐个插入到一个已经排序好的有序序列中
     * 直到所有的记录都插完
     * <p>
     * TODO : 时间复杂度分析, 每一个数都要和前面的每一个数进行比较为 O(N^2)
     *        空间复杂度分析, 没有额外开辟新的空间 O(1)
     *        稳定性分析, 两个元素相等的时候, 不进行交换, 因此还在原地为稳定的排序
     */
    public void insertSort(int[] array) {
        // 一个元素无需排
        if (array.length == 1) {
            return;
        }

        // 以第 2 个位置的元素为开始, 以第一个元素为初始的有序数组
        for (int i = 1; i < array.length; i++) {
            // 记录当前元素
            int tmp = array[i];
            int j = i - 1;
            // 从 i 位置的前一个位置向前的有序数组进行比较
            for (; j >= 0; j--) {
                // 前面的比后面的大, 升序排列交换
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    // 找到了有序数组中比当前要比较数更小的数, 那么这个数之前的数肯定都比这个小
                    // 因此将这个位置更新为 tmp
                    // array[j + 1] = tmp;
                    break; // 直接结束, 锁定该位置
                }
            }

            // 除了插入该位置的值为 tmp, 还起到防止降序排列 j 走到 - 1 位置, 说明此时 tmp 比前面的数组元素都小
            // 则需要主动将第一个位置更新为这个最小的 tmp
            array[j + 1] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] array = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        int[] array1 = {3, 2, 1};
        InsertSort insertSort = new InsertSort();
        insertSort.insertSort(array1);
        System.out.println(Arrays.toString(array1));
    }
}
